// 200.岛屿数量
package LeetcodeHot100;

public class Solution200 {
    class UnionFind {
        int count;
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int xx = grid.length;
            int yy = grid[0].length;
            parent = new int[xx * yy];
            rank = new int[xx * yy];
            for (int i = 0; i < xx; i++) {
                for (int j = 0; j < yy; j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        parent[i * yy + j] = i * yy + j;
                    }
                    rank[i * yy + j] = 0;
                }
            }
        }

        public int find(int i) {
            return parent[i] == i ? i : find(parent[i]);
        }

        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);

            if (rootx != rooty) {
                if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else {
                    parent[rootx] = rooty;
                    rank[rooty]++;
                }
                count--;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        int xx = grid.length;
        int yy = grid[0].length;
        UnionFind uf = new UnionFind(grid);

        for (int i = 0; i < xx; i++) {
            for (int j = 0; j < yy; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    // 组合四个邻接点
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                        uf.union(i * yy + j, (i - 1) * yy + j);
                    }
                    if (i + 1 < xx && grid[i + 1][j] == '1') {
                        uf.union(i * yy + j, (i + 1) * yy + j);
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                        uf.union(i * yy + j, i * yy + j - 1);
                    }
                    if (j + 1 < yy && grid[i][j + 1] == '1') {
                        uf.union(i * yy + j, i * yy + j + 1);
                    }
                }
            }
        }
        return uf.getCount();
    }
}
